package com.love.yushu;

/**
 * 求最大公约数相关的经典题目
 * 一个正整数如果能被 a 或 b 整除，那么它是神奇的。
 * 给定三个整数 n ，a，b，返回第 n 个神奇的数字。
 * 因为答案可能很大，所以返回答案 对 10^9 + 7 取模 后的值。 注意：
 * 本题用到“二分答案法”和“容斥原理”两个重要的算法，不过用的非常浅，之前没有接触过也能理解 “二分答案法”非常巧妙可以解决很多问题，整套内容会在后续的【必备】课程里做成专题视频讲述 “容斥原理”可以考的非常难，也会在后续的【扩展】课程里做成专题视频讲述
 */
public class GongYuShu {


    public static void main(String[] args) {
        int i = nthMagicNumber(1, 2, 3);
        System.out.println(i);
    }

    public static int nthMagicNumber(int n,int a,int b){
        long lcm = lcm(a, b);
        long ans = 0;
        long m = 0;
        for (long l = 0,r = (long) n * Math.min(a,b); l <= r; ) {
            m = l + ((r - l) >> 1);
            if(m / a + m / b - m / lcm >= n){
                ans = m;
                r = m - 1;
            }else {
                l = m + 1;
            }
        }
        return (int) (ans % 1000000007);
    }


    /**
     * 最大公约数
     * @param a
     * @param b
     * @return
     */
    public static long gcd(long a, long b){
        return b == 0 ? a : gcd(b, a % b);
    }

    /**
     * 最小公倍数
     * @param a
     * @param b
     * @return
     */
    public static long lcm(long a,long b){
        return(long) a / gcd(a,b) * b;
    }

}
